package tree;

public class FanZhuanTree {

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left=new Node(2);
        root.right=new Node(3);
        root.left.left=new Node(4);
        root.left.right=new Node(5);
        root.right.left=new Node(6);
        root.right.right=new Node(7);

        fanZhuan(root);

        print(root);
    }

    /*
    思路： 递归对左子树进行翻转
          递归对右子树进行返还
          对根节点左右进行翻转

    1. 递归处理左子树
    2. 递归处理右子树
    3. 交换左右两侧：
        1. 临时变量tmp保存左侧节点
        2. 把根节点的左侧修改成右侧节点
        3. 把根节点的右侧修改成临时节点

    最简问题： root是null，无需翻转
     */
    private static void fanZhuan(Node root){
        if (root==null){
            return;
        }
        fanZhuan(root.left);
        fanZhuan(root.right);
        Node tmp = root.left;
        root.left = root.right;
        root.right=tmp;
    }


    /*先处理左 再中间 再右*/
    private static void print(Node root){
        if (root==null){
            return;
        }
        print(root.left);
        System.out.println(root.value);
        print(root.right);
    }

    /*二叉树的节点类*/
    static class Node{
        int value;
        Node left;
        Node right;
        Node(int value){
            this.value = value;
        }
    }
}
